package net.tp.algo.text.sa;

/**
 *
 * <p>Kasai algorithm for LCP.</p>
 *
 * <p>The key idea of Kasai's algorithm is based on this observation: $\lcp (S_{k+1}, S_{pred(k+1)}) ≥ \lcp (S_k, S_{pred(k)})-1$</p>
 *
 * <p>Example: banana$</p>
 * <pre>
 *      i   sa[i]   lcp[i]       text[sa[i]]
 *      0   6       0            ¥
 *      1   5       0            a¥
 *      2   3       1            ana¥
 *      3   1       3            anana¥
 *      4   0       0            banana¥
 *      5   4       0            na¥
 *      6   2       2            nana¥
 *
 *      i   rank[i] lcp[rank[i]] text[i]
 *      0   4       0            banana¥
 *      1   3       3            anana¥
 *      2   6       2 ≥ 3-1      nana¥
 *      3   2       1 ≥ 2-1      ana¥
 *      4   5       0 ≥ 1-1      na¥
 *      5   1       0            a¥
 *      6   0       0            ¥
 * </pre>
 * <p>{@code rank} is inverse of {@code sa: rank[sa[i]] == i or sa[rank[i]] == i}.</p>
 * <p>We can see that {@code lcp[rank[2]] ≥ lcp[rank[1]] - 1}.</p>
 *
 * <p>Proof:<p>
 * <pre>
 *           ← h →           ← h →
 *     S: ---TEXTS-----------TEXTS--------
 *           ┊┊              ┊┊
 *   pos:    k┊              j┊
 *            k+1             j+1
 *
 *    SA: --------------------------------
 *          ┊      ┊┊          ┊┊
 *          j+1    ┊k+1        jk
 *                 pred(k+1)
 *
 * </pre>
 * <p>Let $j = pred(k)$</p>
 * <p>Let $h = \lcp (S_k, S_j)$, if $h &gt; 0$ then $\lcp (S_{k+1}, S_{j+1}) = h-1$</p>
 * <p>Prove that $\lcp (S_{k+1}, S_{pred(k+1)}) ≥ h-1$. Two ways to prove this:</p>
 * <p>1. As $j = pred(k), i.e. SA_j &lt; SA_k ⇒ S_j &lt; S_k ⇒ S_{j+1} &lt; S_{k+1} ⇒ SA_{j+1} &lt; SA_{k+1} ⇒ SA_{pred(k+1)}$ must position between $SA_{j+1}$ and $SA_{k+1}$. As $S_{j+1}$ and $S_{k+1}$ share the first $h-1$ characters, $S_{pred(k+1)}$ must share at least $h-1$ characters with $S_{k+1}$.</p>
 * <p>2. By visualize the suffix tree containing suffix $S_{j+1}$ and $S_{k+1}$. While traversing the tree, it will visite the leaf node for $S_{j+1}$ first then $S_{pred(k+1)}$, then $S_{k+1}$. Note that it visit the $S_{pred(k+1)}$ right before $S_{k+1}$, so $S_{pred(k+1)}$ must branch after the $S_{j+1}$ branch, making $\lcp (S_{pred(k+1)}) ≥ \lcp (S_{j+1}, S_{k+1}) = h-1$.</p>
 * 
 * <p>Algorithm:</p>
 * <p>Basically, the algorithm to compute LCP based on the above formula is similar to the naive approach where we loop through each character to compare a suffix with its previous suffix to compute lcp. The main difference is that instead of starting from 0, we start from $h-1$ which is the previously computed LCP.</p>
 * <p>Take {@code banana¥} as the example, we will loop through the suffices in the order $S_0, S_1, ..., S_{n-1}$ (or {@code banana¥, anana¥, ...,¥}) to compute LCP for each of these suffices.
 * For each loop, we maintain $h$ to be the previous LCP value, so that in the current loop, we start from $h-1$ instead of 0 to compute the current LCP.</p>
 * 
 *
 * <p>Analysis: why is this linear $O(n)$?</p>
 * <p>Note that in each loop of the algorithm, $h$ decreases at most 1 so in total, $h$ decreases at most $n$. Also, in each loop, $h$ can increase one by one, but $h$ is always less than $n$. So in total, $h$ increases at most $2n$, making this algorithm running in linear time.</p>
 *
 * @author Trung Phan
 * @time $O(n)$
 * @space $O(n)$
 * @see <p>Kasai, T. et al (2001) Linear-Time Longest-Common-Prefix Computation in Sux Arrays and Its Applications</p>
 *
 */
public class KasaiLCP {

    public static int[] buildLCP(String text, int[] sa) {

        int n = text.length();
        assert sa.length == n;

        int[] rank = new int[n];
        for (int i = 0; i < n; i++)
            rank[sa[i]] = i;

        int[] lcp = new int[n];
        for (int h = 0, k = 0; k < n; k++) {

            if (rank[k] > 0) {
                int j = sa[rank[k] - 1]; // j = pred(k)
                while (j+h < n && k+h < n && text.charAt(j+h) == text.charAt(k+h))
                    h++;
            }
            
            lcp[rank[k]] = h;
            if (h > 0) h--;
        }

        return lcp;
    }

}
